{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align: right\"><i>Peter Norvig<br>Aug 2020<br>Revised Jun 2025</i></div>\n",
    "\n",
    "# War [(What is it Good For?)](https://www.youtube.com/watch?v=bX7V6FAoTLc)\n",
    "\n",
    "The [538 Riddler Classic for 28 August 2020](https://fivethirtyeight.com/features/can-you-cover-the-globe/) concerns the children's [**card game War**](https://en.wikipedia.org/wiki/War_%28card_game%29). The column states \"Duane’s friend’s granddaughter claimed that she once won a game of War that lasted exactly 26 turns, with no wars.\" What is the probability of that? We'll analyze this problem, and then we'll look at some other questions about the game. To review, here are the rules:\n",
    "- The deck (typically 52 cards) is dealt out so that the two players each have half the cards (26).\n",
    "- Both players play a card, face up, from the top of their deck. This is called a **battle**.\n",
    "- If there is a tie between the two cards in a battle, a **war** ensues:\n",
    "    - To resolve a war, both players play three cards face down and a fourth face up. (Some variants use only one or two face-down cards.)\n",
    "    - If the fourth (face-up) cards are the same, there is another war.\n",
    "- The player with the higher of the face-up cards wins the battle/war and places all the played cards at the bottom of their deck (in random order).\n",
    "- Repeat play until one player runs out of cards, and thereby loses the game.\n",
    "    - If both players run out of cards at the same time, it is a tie.\n",
    "\n",
    "I considered four approaches:\n",
    "\n",
    "# Approach 1: Simple Arithmetic?\n",
    "\n",
    "Assuming the cards are fairly shuffled, both players have an equal chance of winning each battle. If player **A** wins each battle with probability 1/2, than the probability of sweeping 26 battles in a row would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4901161193847656e-08"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(1/2) ** 26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About **15 in a billion**. But after player **A** plays a card, there are 51 possible cards that player **B** might play. Of these, 3 have the same rank as **A**'s card, resulting in a tie. So the possible outcomes for the first battle are:    \n",
    "\n",
    "    tie:     3/51\n",
    "    A wins: 24/51\n",
    "    B wins: 24/51\n",
    "    \n",
    "If every subsequent battle were the same, the probability that **A** sweeps 26 battles in a row would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0808297965386556e-09"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(24/51) ** 26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About **3 in a billion**.  I have to say, I'm begining to doubt Duane’s friend’s granddaughter's claim! \n",
    "\n",
    "But this answer is still not quite right because the outcome of each battle depends on the cards played in the previous turns. So simple arithmetic gets us an estimate, but not an exact answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approach 2: Brute Force Enumeration?\n",
    "\n",
    "A discrete probability problem like this can be solved, in theory, by enumerating every possibility:\n",
    "- Consider every possible permutation (that is, shuffle) of the deck of cards.\n",
    "- For each permutation, deal out the cards and see whether or not **A** wins every battle.\n",
    "- The probability is the number of sweeps divided by the number of permutations.\n",
    "\n",
    "Easy-peasy; here's the code (with some imports first):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "from collections import Counter, deque, namedtuple\n",
    "from itertools   import permutations, combinations, count as count_from\n",
    "from statistics  import mean, median, stdev, mode\n",
    "from typing      import List, Tuple, Iterable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "Probability = float # Type: Probability is a number between 0.0 and 1.0\n",
    "Deck        = deque # Type: Deck is a sequence of card ranks\n",
    "\n",
    "def make_deck(ranks=13, suits=4) -> Deck: \n",
    "    \"\"\"A Deck is a sequence of ranks, each rank repeated `suits` times.\"\"\"\n",
    "    return Deck(r for r in range(1, ranks + 1) for _ in range(suits)) \n",
    "\n",
    "deck52 = make_deck(13, 4)\n",
    "\n",
    "def is_sweep(deck: Deck) -> bool: \n",
    "    \"\"\"Upon dealing this deck, does player A win every battle?\"\"\"\n",
    "    return all(deck[i] > deck[i + 1] for i in range(0, len(deck), 2))\n",
    "\n",
    "def p_sweep(decks: Iterable[Deck]) -> Probability:\n",
    "    \"\"\"The probability that player A sweeps every battle, averaged over the decks.\"\"\"\n",
    "    return mean(map(is_sweep, decks))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(*Implementation details:* in Python `False` is equivalent to `0` and `True` is equivalent to `1`, so the `mean` of an iterable of `bool` values is the same as the proportion (or probability) of `True` values. I used a `deque` (doubly-ended queue) to represent a deck, because I think of a deck as popping cards off the top and adding cards to the bottom (although we won't add to the bottom until later). Also because \"deck\" and \"deque\" are homophones.)\n",
    "\n",
    "Here are three different 8-card decks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert make_deck(ranks=8, suits=1) == Deck([1, 2, 3, 4, 5, 6, 7, 8])\n",
    "assert make_deck(ranks=4, suits=2) == Deck([1, 1, 2, 2, 3, 3, 4, 4])\n",
    "assert make_deck(ranks=2, suits=4) == Deck([1, 1, 1, 1, 2, 2, 2, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here are the probabilities of sweeping a game played with those decks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0625"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(permutations(make_deck(8, 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.03571428571428571"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(permutations(make_deck(4, 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.014285714285714285"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(permutations(make_deck(2, 4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about the real deck, with 52 cards? Unfortunately, there are 52! permutations (more than $10^{67}$), and even if we were clever about repetitions, and\n",
    "even if we could process a billion deals a second, it would still take [millions of years](https://www.google.com/search?q=%2852%21+%2F+4%21%5E13+%2F+26%21%29+nanoseconds+in+years&oq=%2852%21+%2F+4%21%5E13+%2F+26%21%29+nanoseconds+in+years) to complete the brute force enumeration. And 538 Riddler wanted the answer by Monday!\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approach 3: Random Simulation?\n",
    "\n",
    "It takes too long to look at **all** the permutations, but we can  randomly sample **some** of the permutations of the deck to get an estimated probability. With enough samples this estimate will be close to the true value. The function `shuffles` yields `n` random shuffles of a deck:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shuffles(deck: Deck, n: int) -> Iterable[Deck]:\n",
    "    \"\"\"`n` random shuffles (mutations) of `deck`.\"\"\"\n",
    "    for _ in range(n):\n",
    "        random.shuffle(deck)\n",
    "        yield deck\n",
    "\n",
    "def shuffle(deck: Deck) -> Deck:\n",
    "    \"\"\"A single shuffle of `deck`.\"\"\"\n",
    "    return next(shuffles(deck, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following sample is close to the true value of 0.0625:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.06233"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(shuffles(make_deck(8, 1), 100_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can handle the full 52 card deck, but will the estimate be accurate?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(shuffles(deck52, 100_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The estimate is **0 in 100,000** which is the best possible estimate with that few samples. We  would need trillions of samples to get a decent estimate. That would require weeks of run time: much better than millions of years, but still not good enough. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approach 4: Abstract Incremental Enumeration\n",
    "\n",
    "As discussed in my [**How To Count Things**](How%20To%20Count%20Things.ipynb) notebook, in problems where brute force enumeration is not feasible it is often possible to use a representation that is:\n",
    "- **Incremental**: First we'll consider the possibilities for the two cards in the first battle, and only for the outcomes in which **A** wins will we then move on to look at the possible cards for the next battle. For outcomes in which **A**  loses or ties, there is no need to consider the permutations of the remaining cards.\n",
    "- **Abstract**: What matters on each battle is whether **A**'s next card is higher, lower, or the same as **B**'s next card. On the first battle there are 52 × 3 = 156 ways in which the two players could play the same rank, but it doesn't matter if the ranks are two 3s or two 7s or whatever; the result is the same. So we should have an abstract representation that treats this as one way, not 156. Similarly, there are 52 × 48 = 2496 ways in which the two players could play different ranks, but again it doesn't matter if this is a 3 and a 7; or a 2 and a 10, or whatever. \n",
    "\n",
    "     \n",
    "# Abstract Deck\n",
    "\n",
    "The representation I will use, which I call `AbstractDeck`, is as follows:\n",
    "- An `AbstractDeck` is a tuple of counts of the number of remining cards of each rank, without specifying the ranks. \n",
    "- Ranks with counts of zero are dropped from the representation.\n",
    "- The counts are put in sorted order, lowest counts first.\n",
    "- For example:\n",
    "    - The initial 52-card deck is 13 ranks of 4 cards each: `(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)`\n",
    "    - The possible decks with just 2 cards remaining are `(2,)` and `(1, 1)`; that is, two cards of the same rank or 1 each of two different ranks.\n",
    "    - The possible decks with just 3 cards remaining are `(1, 1, 1)`, `(1, 2)`, and `(3,)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AbstractDeck = tuple # Type: An abstract deck\n",
    "\n",
    "deck52a = AbstractDeck(13 * [4]) # The initial 52-card abstract deck\n",
    "deck52a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">***Note:***  I also thought of an alternative representation in which: \n",
    ">- A deck was a tuple where `deck[i]` gives the number of different ranks that have exactly `i` cards remaining in the deck.\n",
    ">- The initial deck is represented as `(0, 0, 0, 0, 13)`: 13 ranks with 4-of-a-kind; none with less than that.\n",
    ">- The two possible two-card decks are `(0, 2)` (two ranks with 1 card each) and `(0, 0, 1)` (one rank with two cards).\n",
    ">\n",
    ">That representation was more compact, and thus ran a bit faster. But the very nice  [implementation](https://laurentlessard.com/bookproofs/flawless-war/) shared by [Laurent Lessard](https://laurentlessard.com/) convinced me to show the `AbstractDeck` representation because it is simpler to code and to understand.\n",
    "\n",
    "# Probability Distribution\n",
    "\n",
    "We'll keep track of possible outcomes with a class called `ProbDist` (for **probability distribution**), a mapping of `{deck: p}` where `deck` is an abstract deck and `p` is the probability of that deck being the outcome of a battle. For our problem we only need to track the outcomes in which **A** wins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ProbDist(Counter): \n",
    "    \"\"\"A probability distribution of {outcome: probability}.\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Abstract Incremental Enumeration Strategy\n",
    "\n",
    "The probability that **A** sweeps a game of War, `p_sweep_abstract(deck)`, is computed as follows:\n",
    "\n",
    "- Start with `P` being a **probability distribution** of outcomes after 0 battles: `{deck: 1.0}`.\n",
    "- **for** each battle of the game (26 battles for a 52-card deck):\n",
    "  - Update `P` to be the distribution that results from playing a single battle, `P = play_battle(P)`. Do that as follows:\n",
    "  - **for** each `deck` in `P`:\n",
    "      - **for** each way of removing two cards of distinct ranks `i` and `j` from `deck` to yield a resulting deck:\n",
    "          - Increment the probability of the resulting deck by probability of `deck` × probability of  `i` ×  probability of `j` \n",
    "\n",
    "Note that the call `combinations(indexes, 2)` yields all distinct pairs of indexes. Thus it will return `(i, j)` but not also `(j, i)`, and not `(i, i)`. That's just what we want: if the two selected ranks are the same then the result will be a tie, which we don't want in our resulting distribution of winning outcomes. And out of the two possibilities `(i, j)` and `(j, i)`, exactly one will result in a win for **A**, so we only want to include one of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def p_sweep_abstract(deck: AbstractDeck) -> Probability:\n",
    "    \"\"\"The probability that player A sweeps every battle in a game of War.\"\"\"\n",
    "    P = ProbDist({deck: 1.0}) # The initial probability distribution\n",
    "    for _ in range(sum(deck) // 2):\n",
    "        P = play_battle(P)\n",
    "    return P[()]\n",
    "\n",
    "def play_battle(P: ProbDist) -> ProbDist:\n",
    "    \"\"\"Play one battle with all possible card choices for players A and B; return\n",
    "    the probability distribution of outcomes where A still might sweep.\"\"\"\n",
    "    P1 = ProbDist() # The probability distribution of {deck: prob} after this battle\n",
    "    for deck in P:\n",
    "        n = sum(deck) # number of cards in deck\n",
    "        indexes = range(len(deck))\n",
    "        for i, j in combinations(indexes, 2):\n",
    "            P1[remove(deck, i, j)] += P[deck] * deck[i] * deck[j] / (n * (n - 1))\n",
    "    return P1\n",
    "\n",
    "def remove(deck: AbstractDeck, i: int, j: int) -> AbstractDeck:\n",
    "    \"\"\"Remove a card from each of the indexes i and j from the abstract deck.\"\"\"\n",
    "    counts = list(deck)\n",
    "    counts[i] -= 1\n",
    "    counts[j] -= 1\n",
    "    return AbstractDeck(sorted(c for c in counts if c > 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert remove(AbstractDeck((2, 3, 4)), 0, 1) == AbstractDeck((1, 2, 4)) # Test: remove a card from indexes 0 and 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Answer!\n",
    "\n",
    "What's the probability that player **A** will win in a sweep?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.132436174322299e-09"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = p_sweep_abstract(deck52a)\n",
    "p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A little over **3.1 in a billion** (which is slightly higher than the simple arithmetic calculation).\n",
    "\n",
    "(By the way, this computation took about 0.07 seconds, a big improvement over millions of years!) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the answer to *my* question about the probability of **A** sweeping, but 538 Riddler actually posed the question somewhat differently: \"*How many games of War would you expect to play until you had a game that lasted just 26 turns with no wars, like Duane’s friend’s granddaughter?*\" That is, they want to know the inverse of the probability, and they are allowing for either **A** or **B** to sweep. So that would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "159620171.70491105"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 / (2 * p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " We would expect a sweep about once every 160 million games."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Working through the Algorithm\n",
    "\n",
    "Let's work through how `play_battle` works. We'll start with `P` being the initial probability distribution over possible decks, and then play four battles, each time displaying how `P` is updated.\n",
    "\n",
    "At the start of the game there is only one possibility: a deck with 13 suits of 4 cards each:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ProbDist({(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 1.0})"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = ProbDist({deck52a: 1.0})\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now play one battle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ProbDist({(3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.47058823529411703})"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_battle(P) # Battle 1\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is still only one possibility. That makes sense: the only result where **A** still has a chance to sweep is when the two players turned over cards of different ranks, giving us two ranks with three-of-a-kind remaining, and 11 ranks with four-of-a-kind remaining. The probability of **A** winning one battle is 24/51 = 0.47058823529411703.\n",
    "\n",
    "For the second battle, here are the possibilities, depending on what card rank each player plays:\n",
    "\n",
    "|**A**|**B**|**Result**|\n",
    "|-----|-----|----------|\n",
    "|3-card rank|same 3-card rank|tie; not in result P|\n",
    "|4-card rank|same 4-card rank|tie; not in result P|\n",
    "|3-card rank|different 3-card rank|(2, 2, 4, 4, ...)|\n",
    "|4-card rank|different 4-card rank|(3, 3, 3, 3, 4, 4, ...)|\n",
    "|3-card rank|4-card rank|(2, 3, 3, 4, 4, ...)\n",
    "|4-card rank|3-card rank|(2, 3, 3, 4, 4, ...)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ProbDist({(3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.16902761104441777,\n",
       "          (2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.050708283313325234,\n",
       "          (2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.0017286914765906338})"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_battle(P) # Battle 2\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll leave it as an exercise for the reader to verify that the next battle is correct:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ProbDist({(2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4): 0.048550484023396547,\n",
       "          (3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4): 0.043155985798574735,\n",
       "          (2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.010114684171540947,\n",
       "          (1, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.0017981660749406111,\n",
       "          (1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.0004045873668616376,\n",
       "          (2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.00020229368343081878,\n",
       "          (1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 3.065055809557861e-06})"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_battle(P) # Battle 3\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gaining Confidence in the Answer\n",
    "\n",
    "One way to gain confidence: The answer should be close to the arithmetic calculation of $(24/51)^{26}$. Let's compute the ratio of the two probabilities:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0167508045532485"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p  = p_sweep_abstract(deck52a) \n",
    "p2 = (24/51) ** 26\n",
    "p / p2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the two computations are indeed close, differing by 1.675%.\n",
    "\n",
    "Another way to gain confidence: We can verify that there is no difference between the brute force `p_sweep` and the abstract incremental `p_sweep_abstract` for small decks.  That is evidence that the two implementations are either both right, or both wrong in the same way. `p_sweep` takes just a few milliseconds to solve decks of 8 cards or less, but takes about a second to do the 10! (almost 4 million) permutations of ten card decks, so we won't go larger than that while trying combinations of ranks and suits. In all the cases, the two probability calculations are the same (at least for 16 digits)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ranks = 2; suits = 1:  p = 0.50000; ∆ = 0.0000000000000000\n",
      "ranks = 2; suits = 2:  p = 0.16667; ∆ = 0.0000000000000000\n",
      "ranks = 2; suits = 3:  p = 0.05000; ∆ = 0.0000000000000000\n",
      "ranks = 2; suits = 4:  p = 0.01429; ∆ = 0.0000000000000000\n",
      "ranks = 2; suits = 5:  p = 0.00397; ∆ = 0.0000000000000000\n",
      "ranks = 3; suits = 2:  p = 0.06667; ∆ = 0.0000000000000000\n",
      "ranks = 4; suits = 1:  p = 0.25000; ∆ = 0.0000000000000000\n",
      "ranks = 4; suits = 2:  p = 0.03571; ∆ = 0.0000000000000000\n",
      "ranks = 5; suits = 2:  p = 0.01799; ∆ = 0.0000000000000000\n",
      "ranks = 6; suits = 1:  p = 0.12500; ∆ = 0.0000000000000000\n",
      "ranks = 8; suits = 1:  p = 0.06250; ∆ = 0.0000000000000000\n",
      "ranks =10; suits = 1:  p = 0.03125; ∆ = 0.0000000000000000\n"
     ]
    }
   ],
   "source": [
    "biggest_deck = 10\n",
    "\n",
    "sizes = [(r, s) for r in range(2, biggest_deck + 1) for s in range(1, biggest_deck + 1)\n",
    "                if r * s <= biggest_deck and (r * s) % 2 == 0]\n",
    "\n",
    "for (r, s) in sizes:\n",
    "    p1 = p_sweep(permutations(make_deck(r, s)))\n",
    "    p2 = p_sweep_abstract(AbstractDeck(r * [s]))\n",
    "    print(f'ranks ={r:2d}; suits ={s:2d}:  p = {p1:.5f}; ∆ = {abs(p1 - p2):.16f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Winning in 26 Plays, but not 26 Battles\n",
    "\n",
    "We were specifically asked about games in which one player wins 26 battles in a row. But I was curious: what's the probability of winning in 26 **plays**, but with the possibility of wars, so that ther4e are fewer **battles**? Suppose there are 4 wars in the course of a 26-play game. Then each player plays 3 × 4 = 12 face-down cards and 26 - 12 = 14 face-up cards. It is a lot easier to win 14 battles than 26.\n",
    "\n",
    "The function `sweep_with_wars_abstract` mirrors `p_sweep_abstract`, but with these differences: \n",
    "- Instead of just abstract decks, we need to keep track of abstract **states**, which contain an abstract deck as well as the number of face-down cards remaining to be played in a war.\n",
    "- The value returned is the final probability distribution, not just the probability of winning (because there are multiple possible outcomes).\n",
    "- The function`play_battle_or_face_down` is called instead of `play_battle`.\n",
    "   - In `play_battle_or_face_down` we iterate over all `pairs` of indexes, not just `combinations` of distinct indexes,  because we need to consider cases where both players play the same index. (Note this in a battle this means we have to divide the probability of a pair by 2 because **A** has the higher rank of the pair half the time.) The constant `DOWN` is the number of face-down cards in a war. It is set to 3, but you can change it.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "AbstractState = namedtuple('AbstractState', 'down, deck') # Type for abstract state of the game\n",
    "\n",
    "DOWN = 3                                                  # Number of face-down cards in a war\n",
    "\n",
    "def sweep_with_wars_abstract(deck: AbstractDeck) -> ProbDist:\n",
    "    \"\"\"The probability distribution that player A sweeps a game, which might include wars.\"\"\"\n",
    "    P = ProbDist({AbstractState(0, deck): 1.0}) # The initial probability distribution\n",
    "    for _ in range(sum(deck) // 2):\n",
    "        P = play_battle_or_face_down(P)\n",
    "    return P\n",
    "\n",
    "def play_battle_or_face_down(P: ProbDist) -> ProbDist:\n",
    "    \"\"\"Play all possible card choices for players A and B, whether face-down or face-up.\n",
    "    Return the probability distribution of outcomes where A still might sweep.\"\"\"\n",
    "    P1 = ProbDist() # The probability distribution of {state: prob} after this play\n",
    "    for (down, deck) in P:\n",
    "        indexes = [i for i in range(len(deck)) for _ in range(deck[i])]\n",
    "        pairs   = list(combinations(indexes, 2))\n",
    "        p_pair  = P[AbstractState(down, deck)] / len(pairs)                   # The probability of each pair of indexes\n",
    "        for i, j in pairs:\n",
    "            if down > 0:                                                      # We're in a war\n",
    "                P1[AbstractState(down - 1, remove(deck, i, j))] += p_pair\n",
    "            elif i == j:                                                      # We're starting a war\n",
    "                P1[AbstractState(DOWN, remove(deck, i, j))]     += p_pair\n",
    "            else:                                                             # A wins half the time\n",
    "                P1[AbstractState(0, remove(deck, i, j))]        += p_pair / 2\n",
    "    return P1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ProbDist({AbstractState(down=0, deck=()): 1.5476119509914642e-05,\n",
       "          AbstractState(down=1, deck=()): 3.1233217745837868e-06,\n",
       "          AbstractState(down=2, deck=()): 2.0982962265274516e-06,\n",
       "          AbstractState(down=3, deck=()): 1.4095876874120516e-06})"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = sweep_with_wars_abstract(deck52a)\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are four entries in the distribution. In one of them, `down=0`, player **A** wins, but in the other three, both players run out of cards in the middle of a war (which means the game is a tie). Here's the odds of **A** winning in 26 plays:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64615.68091144286"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p26 = P[AbstractState(down=0, deck=())]\n",
    "1 / p26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that **A** wins in 26 plays about once every 64,000 games. That's a lot more than once every 160 million games! Below we see that there will be a tie (where the whole game is one big multi-war, and both players run out of cards in the middle of a war on their 26th play) about once every 150,000 games:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "150802.13870167118"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_tie26 = sum(P[state] for state in P if state.down > 0)\n",
    "1 / p_tie26"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How Long Does a Game of War Last?\n",
    "\n",
    "Let's consider a different question: how long is an average game of war? What is the distribution of game lengths? \n",
    "\n",
    "I see no feasible way of answering this question using simple arithmetic or brute force enumeration, and no easy way to modify the abstract state representation. (After the first 26 plays, players start re-playing the cards they picked up, and the order in which cards were picked up matters, but our abstract representation doesn't represent the order of cards. Another issue is that games can be of unbounded length.) Therefore, I think a **simulation** is best. In the code that follows:\n",
    "- The type `State` is the state of the game after a play:\n",
    "    - A 4-tuple of the cards held by **A**, the cards held by **B**, and (if a war is  in progress), the played cards  and the number of face-down cards left to go.\n",
    "- The type `Game` is an iterable of game states; a history of what happened in the game.\n",
    "- The function `simulate_game` plays a single game, yielding the game state after every play (and before the first play).\n",
    "- The function starts by dealing the deck to players `A` and  `B`; and setting the `played` cards to an empty list.\n",
    "- On each pass through the main loop, each player plays one card from their deck, and there are three possibilities:\n",
    "    - If we are in a war and a face-down card remains to be played (i.e., `down` > 0), we don't look at the face-down cards, just decrement the number of face-down cards remaining.\n",
    "    - Otherwise, if the cards have the same rank, a new war is started.\n",
    "    - Otherwise, the winner is the player with the higher card. They pick up the played cards, shuffle them, and place them on the bottom of their deck."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "State = namedtuple('State', 'A, B, played, down')         # Type fof state of the game\n",
    "Game  = Iterable[State]                                   # Type for a game history\n",
    "\n",
    "def simulate_game(deck: Deck) -> Game:\n",
    "    \"\"\"Deal the cards and play a random game of War, yielding the state each play.\"\"\"\n",
    "    down = 0\n",
    "    played = []\n",
    "    A, B = Deck(list(deck)[0::2]), Deck(list(deck)[1::2]) # Deal cards to A and B\n",
    "    yield State(A, B, played, down)                       # The state at the start of the game\n",
    "    while A and B:\n",
    "        played += [a := A.popleft(), b := B.popleft()]\n",
    "        if down > 0:                                      # In a war: these cards are face-down\n",
    "            down -= 1\n",
    "        elif a == b:                                      # A tie starts a war\n",
    "            down = DOWN\n",
    "        else:                                             # One player wins all the played cards\n",
    "            winner = (A if a > b else B)\n",
    "            winner.extend(shuffle(played))\n",
    "            played = []\n",
    "        yield State(A, B, played, down)                   # The state at the end of a play"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example of playing a single game with a deck of 12 cards. (We set the random seed to make the output reproducible.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "State(A=deque([4, 6, 3, 4, 3, 2]), B=deque([5, 5, 1, 6, 2, 1]), played=[], down=0)\n",
      "State(A=deque([6, 3, 4, 3, 2]), B=deque([5, 1, 6, 2, 1, 5, 4]), played=[], down=0)\n",
      "State(A=deque([3, 4, 3, 2, 6, 5]), B=deque([1, 6, 2, 1, 5, 4]), played=[], down=0)\n",
      "State(A=deque([4, 3, 2, 6, 5, 3, 1]), B=deque([6, 2, 1, 5, 4]), played=[], down=0)\n",
      "State(A=deque([3, 2, 6, 5, 3, 1]), B=deque([2, 1, 5, 4, 6, 4]), played=[], down=0)\n",
      "State(A=deque([2, 6, 5, 3, 1, 2, 3]), B=deque([1, 5, 4, 6, 4]), played=[], down=0)\n",
      "State(A=deque([6, 5, 3, 1, 2, 3, 1, 2]), B=deque([5, 4, 6, 4]), played=[], down=0)\n",
      "State(A=deque([5, 3, 1, 2, 3, 1, 2, 6, 5]), B=deque([4, 6, 4]), played=[], down=0)\n",
      "State(A=deque([3, 1, 2, 3, 1, 2, 6, 5, 4, 5]), B=deque([6, 4]), played=[], down=0)\n",
      "State(A=deque([1, 2, 3, 1, 2, 6, 5, 4, 5]), B=deque([4, 3, 6]), played=[], down=0)\n",
      "State(A=deque([2, 3, 1, 2, 6, 5, 4, 5]), B=deque([3, 6, 4, 1]), played=[], down=0)\n",
      "State(A=deque([3, 1, 2, 6, 5, 4, 5]), B=deque([6, 4, 1, 2, 3]), played=[], down=0)\n",
      "State(A=deque([1, 2, 6, 5, 4, 5]), B=deque([4, 1, 2, 3, 6, 3]), played=[], down=0)\n",
      "State(A=deque([2, 6, 5, 4, 5]), B=deque([1, 2, 3, 6, 3, 1, 4]), played=[], down=0)\n",
      "State(A=deque([6, 5, 4, 5, 1, 2]), B=deque([2, 3, 6, 3, 1, 4]), played=[], down=0)\n",
      "State(A=deque([5, 4, 5, 1, 2, 2, 6]), B=deque([3, 6, 3, 1, 4]), played=[], down=0)\n",
      "State(A=deque([4, 5, 1, 2, 2, 6, 3, 5]), B=deque([6, 3, 1, 4]), played=[], down=0)\n",
      "State(A=deque([5, 1, 2, 2, 6, 3, 5]), B=deque([3, 1, 4, 6, 4]), played=[], down=0)\n",
      "State(A=deque([1, 2, 2, 6, 3, 5, 5, 3]), B=deque([1, 4, 6, 4]), played=[], down=0)\n",
      "State(A=deque([2, 2, 6, 3, 5, 5, 3]), B=deque([4, 6, 4]), played=[1, 1], down=3)\n",
      "State(A=deque([2, 6, 3, 5, 5, 3]), B=deque([6, 4]), played=[1, 1, 2, 4], down=2)\n",
      "State(A=deque([6, 3, 5, 5, 3]), B=deque([4]), played=[1, 1, 2, 4, 2, 6], down=1)\n",
      "State(A=deque([3, 5, 5, 3]), B=deque([]), played=[1, 1, 2, 4, 2, 6, 6, 4], down=0)\n"
     ]
    }
   ],
   "source": [
    "random.seed(32)\n",
    "deck = shuffle(make_deck(6, 2))\n",
    "for state in simulate_game(deck):\n",
    "    print(state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this game there is a war when **B** does not have enough cards left to play 3 face-down and one face-up, so **B** loses.\n",
    "\n",
    "But the format of the output could be improved, so I'll define `show_game` to print in a prettier format:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def show_game(game: Game, col_width=30) -> None:\n",
    "    \"\"\"Show how the game progresses on each play.\"\"\"\n",
    "    def fmt(deck) -> str: return ''.join(map(str, deck)).rjust(col_width)\n",
    "    dash = '-' * col_width\n",
    "    print(f'Play |{fmt(\"A\")} |{fmt(\"B\")} |{fmt(\"played\")} | ↓ | Play\\n'\n",
    "          f'-----+{dash}-+{dash}-+{dash}-+---+-----')\n",
    "    for i, (A, B, played, down) in enumerate(game):\n",
    "        print(f'{i:4} |{fmt(A)} |{fmt(B)} |{fmt(played)} | {down or \"\":1} | {i:2}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Play |                             A |                             B |                        played | ↓ | Play\n",
      "-----+-------------------------------+-------------------------------+-------------------------------+---+-----\n",
      "   0 |                        463432 |                        551621 |                               |   |  0\n",
      "   1 |                         63432 |                       5162154 |                               |   |  1\n",
      "   2 |                        343265 |                        162154 |                               |   |  2\n",
      "   3 |                       4326531 |                         62154 |                               |   |  3\n",
      "   4 |                        326531 |                        215464 |                               |   |  4\n",
      "   5 |                       2653123 |                         15464 |                               |   |  5\n",
      "   6 |                      65312312 |                          5464 |                               |   |  6\n",
      "   7 |                     531231265 |                           464 |                               |   |  7\n",
      "   8 |                    3123126545 |                            64 |                               |   |  8\n",
      "   9 |                     123126545 |                           436 |                               |   |  9\n",
      "  10 |                      23126545 |                          3641 |                               |   | 10\n",
      "  11 |                       3126545 |                         64123 |                               |   | 11\n",
      "  12 |                        126545 |                        412363 |                               |   | 12\n",
      "  13 |                         26545 |                       1236314 |                               |   | 13\n",
      "  14 |                        654512 |                        236314 |                               |   | 14\n",
      "  15 |                       5451226 |                         36314 |                               |   | 15\n",
      "  16 |                      45122635 |                          6314 |                               |   | 16\n",
      "  17 |                       5122635 |                         31464 |                               |   | 17\n",
      "  18 |                      12263553 |                          1464 |                               |   | 18\n",
      "  19 |                       2263553 |                           464 |                            11 | 3 | 19\n",
      "  20 |                        263553 |                            64 |                          1124 | 2 | 20\n",
      "  21 |                         63553 |                             4 |                        112426 | 1 | 21\n",
      "  22 |                          3553 |                               |                      11242664 |   | 22\n"
     ]
    }
   ],
   "source": [
    "random.seed(32)\n",
    "deck = shuffle(make_deck(6, 2))\n",
    "show_game(simulate_game(deck))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we can play a game, we can answer the question: what is the (estimated) distribution of lengths of games? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def game_lengths(deck, N=100_000) -> List[int]: \n",
    "    \"\"\"Lengths (in plays) of N games played from randomly shuffled `deck`.\"\"\"\n",
    "    return [len(list(simulate_game(d))) - 1 # Subtract one because the initial state isn't a play\n",
    "            for d in shuffles(deck, N)]\n",
    "    \n",
    "def show_distribution(numbers: List[int], xlabel='Game length') -> None:\n",
    "    \"\"\"Show a histogram and stats for `numbers`.\"\"\"\n",
    "    print(f'N: {len(numbers):,d}; Mean: {mean(numbers):.0f} ± {stdev(numbers):.0f}\\n'\n",
    "          f'Min: {min(numbers)}; Median: {median(numbers):.0f}; Max: {max(numbers)}; Mode: {mode(numbers)}')\n",
    "    plt.hist(numbers, align='left', bins=75)\n",
    "    plt.xlabel(xlabel); plt.ylabel('Frequency'); plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N: 100,000; Mean: 294 ± 234\n",
      "Min: 26; Median: 224; Max: 2734; Mode: 94\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk0AAAGwCAYAAAC0HlECAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjAsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvlHJYcgAAAAlwSFlzAAAPYQAAD2EBqD+naQAAMApJREFUeJzt3QuczXX+x/HPjHG/X3Jb41Jyiwi7Iuxa1oisWy1RVJYlRO6Tcqm2EVHuarfQpg3/sEWRXBLJLfeYyD3XzWVIM4z5/R+f7+7v7Dlm6GscM+fyej4epzPn9/ue3/meX2fmvH1vvwjHcRwBAADADUXeeDcAAAAUoQkAAMACoQkAAMACoQkAAMACoQkAAMACoQkAAMACoQkAAMBClE0h/LKUlBQ5duyY5M2bVyIiIjK7OgAAwIIuV3nhwgUpWbKkREbeuC2J0OQnGpiio6MzuxoAACAdjhw5IqVKlbphGUKTn2gLk3vS8+XLl9nVAQAAFhISEkyjh/s9fiOEJj9xu+Q0MBGaAAAILjZDaxgIDgAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYIHQBAAAYCHKphCCT9mhi9PcfnB0iwyvCwAAoYCWJgAAAAuEJgAAAAuEJgAAAAuEJgAAAAuEJgAAAAuEJgAAAAuEJgAAAAus0xSi6zEBAAD/oqUJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAAqEJAADAQpRNIYSOskMXp7n94OgWGV4XAACCCS1NAAAAFghNAAAAFghNAAAAFghNAAAAFghNAAAAFghNAAAAgR6aVq9eLS1btpSSJUtKRESELFy40Ge/4zgyfPhwKVGihOTMmVOaNGkie/fu9Slz5swZ6dSpk+TLl08KFCggXbt2lYsXL/qU2b59uzRo0EBy5Mgh0dHRMmbMmFR1mTdvnlSqVMmUqVatmnzyySe36V0DAIBglKmh6aeffpLq1avLlClT0tyv4WbixIkyffp0Wb9+veTOnVtiYmIkMTHRU0YD065du2TZsmWyaNEiE8S6d+/u2Z+QkCBNmzaVMmXKyObNm2Xs2LEycuRIeeuttzxlvvrqK3n00UdN4NqyZYu0bt3a3Hbu3HmbzwAAAAgWEY425wQAbWlasGCBCStKq6UtUAMGDJCBAweabefPn5dixYrJzJkzpUOHDrJ7926pUqWKbNy4UWrXrm3KLFmyRJo3by5Hjx41z582bZoMGzZMTpw4IdmyZTNlhg4dalq19uzZYx63b9/eBDgNXa77779fatSoYQJbWpKSkszNO5xpK5bWUVu9MnuxypvF4pYAgHCUkJAg+fPnt/r+DtgxTQcOHDBBR7vkXPqm6tSpI+vWrTOP9V675NzApLR8ZGSkaZlyyzRs2NATmJS2VsXHx8vZs2c9Zbxfxy3jvk5a4uLiTH3cmwYmAAAQugI2NGlgUtqy5E0fu/v0vmjRoj77o6KipFChQj5l0jqG92tcr4y7Py2xsbEmlbq3I0eO3MK7BQAAgY5rz6VT9uzZzQ0AAISHgG1pKl68uLk/efKkz3Z97O7T+1OnTvnsT05ONjPqvMukdQzv17heGXc/AABAwIamcuXKmdCyfPlyn8FaOlapbt265rHenzt3zsyKc61YsUJSUlLM2Ce3jM6ou3LliqeMzrSrWLGiFCxY0FPG+3XcMu7rAAAAZGpo0vWUtm7dam7u4G/9+fDhw2Y2Xb9+/eTll1+Wjz76SHbs2CGdO3c2M+LcGXaVK1eWZs2aSbdu3WTDhg2ydu1a6d27t5lZp+VUx44dzSBwXU5AlyaYM2eOTJgwQfr37++pR9++fc2su3HjxpkZdbokwaZNm8yxAAAAMn1MkwaTRo0aeR67QaZLly5mWYHBgwebpQB03SVtUapfv74JN7oApWv27Nkm3DRu3NjMmmvXrp1Z28mlM9s+++wz6dWrl9SqVUuKFCliFsz0XsupXr168v7778vzzz8vzz33nNx9991mSYKqVatm2LkAAACBLWDWaQqndR78iXWaAAAI83WaAAAAAgmhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwEKUTSGEvrJDF6e5/eDoFhleFwAAAhEtTQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAABYITQAAAMEemq5evSovvPCClCtXTnLmzCl33XWXvPTSS+I4jqeM/jx8+HApUaKEKdOkSRPZu3evz3HOnDkjnTp1knz58kmBAgWka9eucvHiRZ8y27dvlwYNGkiOHDkkOjpaxowZk2HvEwAABL6ADk2vvvqqTJs2TSZPniy7d+82jzXMTJo0yVNGH0+cOFGmT58u69evl9y5c0tMTIwkJiZ6ymhg2rVrlyxbtkwWLVokq1evlu7du3v2JyQkSNOmTaVMmTKyefNmGTt2rIwcOVLeeuutDH/PAAAgMEU43s02Aeahhx6SYsWKydtvv+3Z1q5dO9Oi9N5775lWppIlS8qAAQNk4MCBZv/58+fNc2bOnCkdOnQwYatKlSqyceNGqV27timzZMkSad68uRw9etQ8X4PZsGHD5MSJE5ItWzZTZujQobJw4ULZs2ePVV01eOXPn9+8vrZoZZSyQxff1uMfHN3ith4fAIDMdDPf3wHd0lSvXj1Zvny5fPfdd+bxtm3bZM2aNfLggw+axwcOHDBBR7vkXPrG69SpI+vWrTOP9V675NzApLR8ZGSkaZlyyzRs2NATmJS2VsXHx8vZs2fTrFtSUpI50d43AAAQuqIkgGlrj4aRSpUqSZYsWcwYp7/+9a+mu01pYFLasuRNH7v79L5o0aI++6OioqRQoUI+ZXTc1LXHcPcVLFgwVd3i4uJk1KhRfn2/AAAgcAV0S9PcuXNl9uzZ8v7778s333wjs2bNktdee83cZ7bY2FjTlOfejhw5ktlVAgAA4drSNGjQINPapGOTVLVq1eTQoUOmladLly5SvHhxs/3kyZNm9pxLH9eoUcP8rGVOnTrlc9zk5GQzo859vt7rc7y5j90y18qePbu5AQCA8BDQLU2XLl0yY4+8aTddSkqK+Vm71DTU6Lgnl3bn6VilunXrmsd6f+7cOTMrzrVixQpzDB375JbRGXVXrlzxlNGZdhUrVkyzaw4AAISfgA5NLVu2NGOYFi9eLAcPHpQFCxbI+PHjpU2bNmZ/RESE9OvXT15++WX56KOPZMeOHdK5c2czI65169amTOXKlaVZs2bSrVs32bBhg6xdu1Z69+5tWq+0nOrYsaMZBK7rN+nSBHPmzJEJEyZI//79M/X9AwCAwBHQSw5cuHDBLG6pYUm72DTkPProo2YxS3emm1Z/xIgRZk0lbVGqX7++TJ06VSpUqOA5jnbFaVD6+OOPTcuVLlugazvlyZPHZ3HLXr16maUJihQpIn369JEhQ4ZY1zVUlxy4HpYiAACEgpv5/g7o0BRMCE0AAASfkFmnCQAAIFAQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAACwQmgAAAG5XaNq/f396ngYAABBeoal8+fLSqFEjee+99yQxMdH/tQIAAAiF0PTNN9/IvffeK/3795fixYvLX/7yF9mwYYP/awcAABDMoalGjRoyYcIEOXbsmLzzzjty/PhxqV+/vlStWlXGjx8vp0+f9n9NAQAAgnUgeFRUlLRt21bmzZsnr776quzbt08GDhwo0dHR0rlzZxOmAAAAJNxD06ZNm+Tpp5+WEiVKmBYmDUzff/+9LFu2zLRCtWrVyn81BQAAyERR6XmSBqQZM2ZIfHy8NG/eXN59911zHxn5nwxWrlw5mTlzppQtW9bf9QUAAAie0DRt2jR56qmn5IknnjCtTGkpWrSovP3227daPwAAgOANTXv37v3FMtmyZZMuXbqk5/AAAAChMaZJu+Z08Pe1dNusWbP8US8AAIDgD01xcXFSpEiRNLvkXnnlFX/UCwAAIPhD0+HDh81g72uVKVPG7AMAAAg16QpN2qK0ffv2VNu3bdsmhQsX9ke9AAAAgj80Pfroo/LMM8/IypUr5erVq+a2YsUK6du3r3To0MH/tQQAAAjG2XMvvfSSHDx4UBo3bmxWBVcpKSlmFXDGNIWHskMXp7n94OgWGV4XAAACNjTpcgJz5swx4Um75HLmzCnVqlUzY5oAAABCUbpCk6tChQrmBgAAEOrSFZp0DJNeJmX58uVy6tQp0zXnTcc3AQAASLiHJh3wraGpRYsWUrVqVYmIiPB/zQAAAII9NH3wwQcyd+5cc5FeAACAcBCZ3oHg5cuX939tAAAAQik0DRgwQCZMmCCO4/i/RgAAAKHSPbdmzRqzsOWnn34q99xzj2TNmtVn//z58/1VPwAAgOANTQUKFJA2bdr4vzYAAAChFJpmzJjh/5oAAACE2pgmlZycLJ9//rm8+eabcuHCBbPt2LFjcvHiRX/WDwAAIHhD06FDh8xlU1q1aiW9evWS06dPm+2vvvqqDBw40K8V/OGHH+Sxxx6TwoULey7XsmnTJs9+HYw+fPhwKVGihNnfpEkT2bt3r88xzpw5I506dZJ8+fKZrsWuXbumCnfbt2+XBg0aSI4cOSQ6OlrGjBnj1/cBAADCMDTp4pa1a9eWs2fPmqDi0nFOukq4v+jxH3jgATPQXAedf/vttzJu3DgpWLCgp4yGm4kTJ8r06dNl/fr1kjt3bomJiZHExERPGQ1Mu3btkmXLlsmiRYtk9erV0r17d8/+hIQEadq0qbl23ubNm2Xs2LEycuRIeeutt/z2XgAAQBiOafryyy/lq6++Mus1eStbtqxpGfIXbbnSVh/vMVTlypXzaWV644035PnnnzetXurdd9+VYsWKycKFC6VDhw6ye/duWbJkiWzcuNEEPTVp0iSzMOdrr70mJUuWlNmzZ8vly5flnXfeMe9JZwRu3bpVxo8f7xOuvCUlJZmbd/ACAAChK10tTXqtOb3+3LWOHj0qefPmFX/56KOPTNB55JFHpGjRonLffffJ3/72N8/+AwcOyIkTJ0yXnCt//vxSp04dWbdunXms99ol5wYmpeUjIyNNy5RbpmHDhj4hUFur4uPjTWtXWuLi4sxruTcNdwAAIHSlKzRpV5a28Lj02nM6RmjEiBF+vbTK/v37Zdq0aXL33XfL0qVLpWfPnvLMM8/IrFmzzH4NTEpblrzpY3ef3mvg8hYVFSWFChXyKZPWMbxf41qxsbFy/vx5z+3IkSN+e98AACBEuud0XJG2xFSpUsWMHerYsaMZfF2kSBH55z//6bfKaYuWthC98sor5rG2NO3cudOMX+rSpYtkpuzZs5sbAAAID+kKTaVKlZJt27aZC/fqrDNtZdIZaTrg2ntg+K3SGXEazLxVrlxZPvzwQ/Nz8eLFzf3JkydNWZc+rlGjhqfMqVOnUi2XoDPq3OfrvT7Hm/vYLQMAAMJbVLqfGBVllgK4nXTmnI4r8vbdd9+ZWW7uoHANNTpjzw1JOiBbxyppV56qW7eunDt3zsyKq1Wrltm2YsUK04qlY5/cMsOGDZMrV654LgmjM+0qVqzoM1MPAACEr3SFJp2hdiOdO3cWf3j22WelXr16pnvuT3/6k2zYsMEsA+AuBaBjqfr16ycvv/yyGfekIeqFF14wM+Jat27taZlq1qyZdOvWzXTraTDq3bu3mVmn5ZR2L44aNcq0lg0ZMsR0AeoFiV9//XW/vA8AABD8Ihydt3+Trm190SBy6dIlM/ssV65cpuvLX3RdJR10rWOmNBT179/fBCCXVl8HoGuQ0hal+vXry9SpU6VChQqeMlofDUoff/yxmTXXrl07s7ZTnjx5PGW0m1EX6tSlCXRsVp8+fUyAsqUtXDqLTgeF6yKaGaXs0MUSDA6ObpHZVQAA4Ja+v9MVmtKioUa7xAYNGmQGiYcbQtONEZoAAMH+/Z3ua89dS7vHRo8ebVYLBwAACDV+C03u4HC9aC8AAECoiUrvSt3etIfv+PHjMnnyZDPjDQAAINSkKzS5M9NcOovtjjvukN///vdm4UsAAIBQk67QpGscAQAAhBO/jmkCAAAIVelqadK1kmyNHz8+PS8BAAAQ/KFpy5Yt5qaLWuqlRtzLm2TJkkVq1qzpM9YJAAAgbENTy5YtJW/evDJr1izP6uBnz56VJ598Uho0aCADBgzwdz0BAACCb0yTzpCLi4vzuZyK/qzXgGP2HAAACEWR6V1y/PTp06m267YLFy74o14AAADBH5ratGljuuLmz58vR48eNbcPP/xQunbtKm3btvV/LQEAAIJxTNP06dNl4MCB0rFjRzMY3BwoKsqEprFjx/q7jgAAAMEZmnLlyiVTp041Aen777832+666y7JnTu3v+sHAAAQ/Itb6vXm9Hb33XebwKTXoAMAAAhF6QpNP/74ozRu3FgqVKggzZs3N8FJafccyw0AAIBQlK7Q9Oyzz0rWrFnl8OHDpqvO1b59e1myZIk/6wcAABC8Y5o+++wzWbp0qZQqVcpnu3bTHTp0yF91AwAACO6Wpp9++smnhcl15swZyZ49uz/qBQAAEPyhSS+V8u677/pcYy4lJUXGjBkjjRo18mf9AAAAgrd7TsORDgTftGmTXL58WQYPHiy7du0yLU1r1671fy0BAACCsaWpatWq8t1330n9+vWlVatWprtOVwLfsmWLWa8JAABAwr2lSVcAb9asmVkVfNiwYbenVgAAAMHe0qRLDWzfvv321AYAACCUuucee+wxefvtt/1fGwAAgFAaCJ6cnCzvvPOOfP7551KrVq1U15wbP368v+oHAAAQfKFp//79UrZsWdm5c6fUrFnTbNMB4d50+QEAAICwDk264rdeZ27lypWey6ZMnDhRihUrdrvqBwAAEHxjmhzH8Xn86aefmuUGAAAAQl26xjRdL0QB11N26OI0tx8c3SLD6wIAwG1vadLxSteOWWIMEwAACAdRN9uy9MQTT3guypuYmCg9evRINXtu/vz5/q0lAABAMIWmLl26pFqvCQAAIBzcVGiaMWPG7asJAABAqK0IDgAAEG4ITQAAALd7yQFk/pR9AACQMWhpAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsEBoAgAAsMAFexGQFyI+OLpFhtcFAIAboaUJAAAg1ELT6NGjJSIiQvr16+fZlpiYKL169ZLChQtLnjx5pF27dnLy5Emf5x0+fFhatGghuXLlkqJFi8qgQYMkOTnZp8yqVaukZs2akj17dilfvrzMnDkzw94XAAAIfEETmjZu3Chvvvmm3HvvvT7bn332Wfn4449l3rx58sUXX8ixY8ekbdu2nv1Xr141geny5cvy1VdfyaxZs0wgGj58uKfMgQMHTJlGjRrJ1q1bTSj785//LEuXLs3Q9wgAAAJXUISmixcvSqdOneRvf/ubFCxY0LP9/Pnz8vbbb8v48ePl97//vdSqVUtmzJhhwtHXX39tynz22Wfy7bffynvvvSc1atSQBx98UF566SWZMmWKCVJq+vTpUq5cORk3bpxUrlxZevfuLQ8//LC8/vrrmfaeAQBAYAmK0KTdb9oS1KRJE5/tmzdvlitXrvhsr1SpkpQuXVrWrVtnHut9tWrVpFixYp4yMTExkpCQILt27fKUufbYWsY9RlqSkpLMMbxvAAAgdAX87LkPPvhAvvnmG9M9d60TJ05ItmzZpECBAj7bNSDpPreMd2By97v7blRGg9DPP/8sOXPmTPXacXFxMmrUKD+8QwAAEAwCuqXpyJEj0rdvX5k9e7bkyJFDAklsbKzpHnRvWlcAABC6Ajo0affbqVOnzKy2qKgoc9PB3hMnTjQ/a2uQjks6d+6cz/N09lzx4sXNz3p/7Ww69/EvlcmXL1+arUxKZ9npfu8bAAAIXQEdmho3biw7duwwM9rcW+3atc2gcPfnrFmzyvLlyz3PiY+PN0sM1K1b1zzWez2Ghi/XsmXLTMipUqWKp4z3Mdwy7jEAAAACekxT3rx5pWrVqj7bcufObdZkcrd37dpV+vfvL4UKFTJBqE+fPibs3H///WZ/06ZNTTh6/PHHZcyYMWb80vPPP28Gl2trkerRo4dMnjxZBg8eLE899ZSsWLFC5s6dK4sXp71aNQAACD8BHZps6LIAkZGRZlFLndGms96mTp3q2Z8lSxZZtGiR9OzZ04QpDV1dunSRF1980VNGlxvQgKRrPk2YMEFKlSolf//7382xAAAAVITjOA6n4tbpTLv8+fObQeG3Y3zT9a7RFqq49hwAINC+vwN6TBMAAECgIDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAACEwzpNCE3XW2KBpQgAAJmFliYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALhCYAAAALUTaFgEBRdujiNLcfHN0iw+sCAAgvtDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAABYIDQBAABY4DIqCAlcXgUAcLvR0gQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCB0AQAAGCBa88hpHFNOgCAv9DSBAAAYIHQBAAAEOyhKS4uTn79619L3rx5pWjRotK6dWuJj4/3KZOYmCi9evWSwoULS548eaRdu3Zy8uRJnzKHDx+WFi1aSK5cucxxBg0aJMnJyT5lVq1aJTVr1pTs2bNL+fLlZebMmRnyHgEAQHAI6ND0xRdfmED09ddfy7Jly+TKlSvStGlT+emnnzxlnn32Wfn4449l3rx5pvyxY8ekbdu2nv1Xr141geny5cvy1VdfyaxZs0wgGj58uKfMgQMHTJlGjRrJ1q1bpV+/fvLnP/9Zli5dmuHvGQAABKYIx3EcCRKnT582LUUajho2bCjnz5+XO+64Q95//315+OGHTZk9e/ZI5cqVZd26dXL//ffLp59+Kg899JAJU8WKFTNlpk+fLkOGDDHHy5Ytm/l58eLFsnPnTs9rdejQQc6dOydLlixJsy5JSUnm5kpISJDo6GhTp3z58mXYgGakDwPBAQDu93f+/Pmtvr8DuqXpWvqGVKFChcz95s2bTetTkyZNPGUqVaokpUuXNqFJ6X21atU8gUnFxMSYk7Rr1y5PGe9juGXcY1yv61BPsnvTwAQAAEJX0ISmlJQU0232wAMPSNWqVc22EydOmJaiAgUK+JTVgKT73DLegcnd7+67URkNVj///HOa9YmNjTUhzr0dOXLEj+8WAAAEmqBZp0nHNmn32Zo1ayQQ6IBxvQEAgPAQFKGpd+/esmjRIlm9erWUKlXKs7148eJmgLeOPfJubdLZc7rPLbNhwwaf47mz67zLXDvjTh9r32bOnDlv63tD5mDRSwBASHXP6Rh1DUwLFiyQFStWSLly5Xz216pVS7JmzSrLly/3bNMlCXSJgbp165rHer9jxw45deqUp4zOxNNAVKVKFU8Z72O4ZdxjAAAARAV6l5zOjPvXv/5l1mpyxyDpwGttAdL7rl27Sv/+/c3gcA1Cffr0MWFHZ84pXaJAw9Hjjz8uY8aMMcd4/vnnzbHd7rUePXrI5MmTZfDgwfLUU0+ZgDZ37lwzow4AACDgW5qmTZtmBln/7ne/kxIlSnhuc+bM8ZR5/fXXzZICuqilLkOgXW3z58/37M+SJYvp2tN7DVOPPfaYdO7cWV588UVPGW3B0oCkrUvVq1eXcePGyd///nczgw4AACDo1mkKlXUe0oN1mjIGY5oAILwkhOo6TQAAAJmF0AQAAGCB0AQAABDss+eAjMb6TQCA66GlCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwAKhCQAAwALrNAEWWL8JAEBLEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAWWHABuAUsRAED4oKUJAADAAqEJAADAAqEJAADAAmOagNuAsU4AEHpoaQIAALBAaAIAALBAaAIAALDAmCYgAzHWCQCCFy1NAAAAFghNAAAAFghNAAAAFghNAAAAFhgIDgQABogDQOCjpQkAAMACoQkAAMAC3XNAAKPbDgACBy1NAAAAFghNAAAAFghNAAAAFhjTBAQhxjoBQMajpQkAAMACLU1ACKEFCgBuH1qaAAAALNDSBIQBWqAA4NbR0gQAAGCBliYgjNECBQD2CE0AUiFMAUBqdM8BAABYoKUJgDVaoACEM0ITgFtGmAIQDghNADI8TN0swheAQMCYJgAAAAu0NF1jypQpMnbsWDlx4oRUr15dJk2aJL/5zW8yu1pAWKP7D0AgIDR5mTNnjvTv31+mT58uderUkTfeeENiYmIkPj5eihYtmtnVA3CL3X+ELAC3IsJxHOeWjhBCNCj9+te/lsmTJ5vHKSkpEh0dLX369JGhQ4fe8LkJCQmSP39+OX/+vOTLly9gx4YAuH0IZUDwuZnvb1qa/uvy5cuyefNmiY2N9WyLjIyUJk2ayLp161KVT0pKMjeXnmz35N8OKUmXbstxAfhP6WfnZXYVAsLOUTGZXQXAmvu9bdOGRGj6r3//+99y9epVKVasmM92fbxnz55U5ePi4mTUqFGptmvLFACEs/xvZHYNgJt34cIF0+J0I4SmdNIWKR3/5NKuvDNnzkjhwoUlIiLCb+lXQ9iRI0duS5dfuOF8+g/n0n84l/7DufSvcDmfjuOYwFSyZMlfLEto+q8iRYpIlixZ5OTJkz7b9XHx4sVTlc+ePbu5eStQoMBtqZt+WEP5A5vROJ/+w7n0H86l/3Au/Ssczmf+X2hhcrFO039ly5ZNatWqJcuXL/dpPdLHdevWzdS6AQCAzEdLkxftbuvSpYvUrl3brM2kSw789NNP8uSTT2Z21QAAQCYjNHlp3769nD59WoYPH24Wt6xRo4YsWbIk1eDwjKLdfyNGjEjVDYj04Xz6D+fSfziX/sO59C/OZ2qs0wQAAGCBMU0AAAAWCE0AAAAWCE0AAAAWCE0AAAAWCE0BbMqUKVK2bFnJkSOHuZjwhg0bMrtKAWfkyJFmBXbvW6VKlTz7ExMTpVevXmal9jx58ki7du1SLWB6+PBhadGiheTKlUuKFi0qgwYNkuTkZAl1q1evlpYtW5pVcPW8LVy40Ge/zhHRmaQlSpSQnDlzmusw7t2716eMroLfqVMns/CdLu7atWtXuXjxok+Z7du3S4MGDcznWFcXHjNmjITbuXziiSdSfU6bNWvmU4Zz+b9LVOmF0/PmzWt+H1u3bi3x8fE+Zfz1e71q1SqpWbOmmR1Wvnx5mTlzpoTbufzd736X6rPZo0cPnzKcSy86ew6B54MPPnCyZcvmvPPOO86uXbucbt26OQUKFHBOnjyZ2VULKCNGjHDuuece5/jx457b6dOnPft79OjhREdHO8uXL3c2bdrk3H///U69evU8+5OTk52qVas6TZo0cbZs2eJ88sknTpEiRZzY2Fgn1Ol7HTZsmDN//nydQessWLDAZ//o0aOd/PnzOwsXLnS2bdvm/PGPf3TKlSvn/Pzzz54yzZo1c6pXr+58/fXXzpdffumUL1/eefTRRz37z58/7xQrVszp1KmTs3PnTuef//ynkzNnTufNN990wulcdunSxZwr78/pmTNnfMpwLv8jJibGmTFjhnmPW7dudZo3b+6ULl3auXjxol9/r/fv3+/kypXL6d+/v/Ptt986kyZNcrJkyeIsWbLECadz+dvf/tZ8v3h/NvWz5uJc+iI0Bajf/OY3Tq9evTyPr1696pQsWdKJi4vL1HoFYmjSL5q0nDt3zsmaNaszb948z7bdu3ebL7V169aZx/oHIDIy0jlx4oSnzLRp05x8+fI5SUlJTri49os+JSXFKV68uDN27Fif85k9e3bzZa30j6M+b+PGjZ4yn376qRMREeH88MMP5vHUqVOdggUL+pzLIUOGOBUrVnRC1fVCU6tWra77HM7l9Z06dcqcmy+++MKvv9eDBw82/+Dy1r59exM0wuVcuqGpb9++130O59IX3XMB6PLly7J582bTHeKKjIw0j9etW5epdQtE2mWk3SJ33nmn6d7QpmSl5/DKlSs+51G77kqXLu05j3pfrVo1nwVMY2JizIUqd+3aJeHqwIEDZoFX73On12bSbmLvc6fdSLqCvkvL62d1/fr1njINGzY0lynyPr/aRXD27FkJJ9p9oV0bFStWlJ49e8qPP/7o2ce5vL7z58+b+0KFCvn191rLeB/DLRPKf2OvPZeu2bNnm+uvVq1a1VyM/tKlS559nEtfrAgegP7973/L1atXU61Ero/37NmTafUKRPolrn3n+kV0/PhxGTVqlBnzsXPnTvOlr18w115IWc+j7lN6n9Z5dveFK/e9p3VuvM+dhgBvUVFR5g+yd5ly5cqlOoa7r2DBghIOdPxS27Ztzbn4/vvv5bnnnpMHH3zQfKnohcI5l2nT63/269dPHnjgAfOFrvz1e329MhoGfv75ZzOOL9TPperYsaOUKVPG/MNTx8wNGTLEBPH58+eb/ZxLX4QmBDX94nHde++9JkTpH4C5c+eG1C8qgluHDh08P+u/2vWzetddd5nWp8aNG2dq3QKZDvbWfwCtWbMms6sSsueye/fuPp9Nnfihn0kN9/oZhS+65wKQNpPqvz6vnQ2ij4sXL55p9QoG+q/PChUqyL59+8y50q7Oc+fOXfc86n1a59ndF67c936jz6Denzp1yme/zqjRWWCc3xvTrmT9PdfPqeJcpta7d29ZtGiRrFy5UkqVKuXZ7q/f6+uV0dmLofYPruudy7ToPzyV92eTc/k/hKYApE3PtWrVkuXLl/s0rerjunXrZmrdAp1O0dZ/Iem/lvQcZs2a1ec8arOzjnlyz6Pe79ixw+cLa9myZeaXvUqVKhKutBtI/xB6nzttatfxNd7nTr+4dIyJa8WKFeaz6v7h1TI6HV/HoHifX+1ODcXuJFtHjx41Y5r0c6o4l/+jY+n1S37BggXmHFzbJemv32st430Mt0wo/Y39pXOZlq1bt5p7788m59LLNQPDEUBLDuhMpZkzZ5qZNd27dzdLDnjPYIDjDBgwwFm1apVz4MABZ+3atWZarE6H1Vki7tRknWK7YsUKMzW5bt265nbtdNqmTZuaKbk6RfaOO+4IiyUHLly4YKYQ603/FIwfP978fOjQIc+SA/qZ+9e//uVs377dzP5Ka8mB++67z1m/fr2zZs0a5+677/aZJq8znXSa/OOPP26mPevnWqcmh9o0+RudS903cOBAM7NLP6eff/65U7NmTXOuEhMTPcfgXP5Hz549zVIX+nvtPQ3+0qVLnjL++L12p8kPGjTIzL6bMmVKyE2T/6VzuW/fPufFF18051A/m/q7fueddzoNGzb0HINz6YvQFMB0rQv9w6DrNekSBLp+C5xU01pLlChhztGvfvUr81j/ELj0C/7pp582U7X1l7pNmzbmj4a3gwcPOg8++KBZ80YDlwaxK1euOKFu5cqV5gv+2ptOj3eXHXjhhRfMF7UG+MaNGzvx8fE+x/jxxx/NF3uePHnMFOQnn3zShARvusZT/fr1zTH0/5GGsXA6l/oFpV84+kWjU+XLlClj1sW59h9AnMv/SOs86k3XG/L377X+f6tRo4b5+6Fhwfs1wuFcHj582ASkQoUKmc+Urg2mwcd7nSbFufyfCP2Pd8sTAAAAUmNMEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwAAgAVCEwDchIiICFm4cKEEgpEjR0qNGjUyuxpA2CA0Acg0J06ckL59+0r58uUlR44cUqxYMXnggQdk2rRpcunSpcyuXkAJpLAGhKuozK4AgPC0f/9+E5AKFCggr7zyilSrVk2yZ89urqj+1ltvya9+9Sv54x//mNnVBAAPWpoAZIqnn35aoqKiZNOmTfKnP/1JKleuLHfeeae0atVKFi9eLC1btvSUHT9+vAlVuXPnlujoaPPcixcvevbPnDnThK9FixZJxYoVJVeuXPLwww+b1qpZs2ZJ2bJlpWDBgvLMM8/I1atXPc9LSkqSgQMHmoCmx65Tp46sWrXqpt7HkSNHTP319QsVKmTqf/DgQc/+J554Qlq3bi2vvfaalChRQgoXLiy9evWSK1eueMocP35cWrRoITlz5pRy5crJ+++/b+r8xhtvmP36s2rTpo1pcXIfu/7xj3+Ybfnz55cOHTrIhQsXbuo9ALBDaAKQ4X788Uf57LPPTHjQsJIWDQeuyMhImThxouzatcuEoBUrVsjgwYN9ymtA0jIffPCBLFmyxIQfDRmffPKJuWmwePPNN+X//u//PM/p3bu3rFu3zjxn+/bt8sgjj0izZs1k7969Vu9Dg09MTIzkzZtXvvzyS1m7dq3kyZPHHOPy5cuecitXrpTvv//e3Gv9NeTpzdW5c2c5duyYqfOHH35oWtpOnTrl2b9x40ZzP2PGDBOw3MdKj6vddhoY9fbFF1/I6NGjreoP4CY5AJDBvv76a0f//MyfP99ne+HChZ3cuXOb2+DBg6/7/Hnz5pmyrhkzZpjj7du3z7PtL3/5i5MrVy7nwoULnm0xMTFmuzp06JCTJUsW54cffvA5duPGjZ3Y2Njrvra+zoIFC8zP//jHP5yKFSs6KSkpnv1JSUlOzpw5naVLl5rHXbp0ccqUKeMkJyd7yjzyyCNO+/btzc+7d+82x9y4caNn/969e822119/Pc3XdY0YMcK8x4SEBM+2QYMGOXXq1Llu/QGkH2OaAASMDRs2SEpKinTq1Ml0nbk+//xziYuLkz179khCQoIkJydLYmKiaV3Srjil93fddZfnOTqoXLustOXHe5vbgqNjp7SrrkKFCj510NfVLjQb27Ztk3379pmWJm9aN20Bct1zzz2SJUsWz2PtptPXV/Hx8aabsmbNmp79OjBeuxNt6Hv0fn09tncrFQD/ITQByHAaCrT7TQODNx3TpHRsj0vHBz300EPSs2dP+etf/2rGDa1Zs0a6du1qusDc0JQ1a1afY+nx09qmoUzpmCgNMps3b/YJNMo7aN2IHqNWrVoye/bsVPvuuOMOz883qsetup3HBuCL0AQgw2lLzh/+8AeZPHmy9OnT57rjmpSGGg0B48aNM2Ob1Ny5c2+5Dvfdd59padJWmQYNGqTrGNo6NGfOHClatKjky5cvXcfQgevacrZlyxYTwJS2Xp09ezZVOPIexA4g4zEQHECmmDp1qgkLtWvXNsFj9+7dpuXpvffeM91wbuuPtkrpgOtJkyaZZQp0QPf06dNv+fW1W067AXUQ9vz58+XAgQOme1C7AXX2ng19fpEiRcyMOR0IrsfQwdw6S+/o0aNWx6hUqZI0adJEunfvbl5fw5P+rK1t3oPhtRtu+fLlZm2rawMVgIxBaAKQKXT8kQYEDQyxsbFSvXp1E6A0HOkyAC+99JIpp9t1yYFXX31VqlatarrCNNj4g85G09A0YMAA0+KjSwPozLTSpUtbPV+7BlevXm3Kt23b1iyboN2GOqbpZlqe3n33XTPeqmHDhmbGX7du3cw4JV3w06UtbcuWLTNLLmgrGYCMF6GjwTPhdQEA16GtVBqOdAB848aNM7s6AP6L0AQAmUzXndJB5bqAp67DpGtQ/fDDD/Ldd9+lGugNIPMwEBwAMpmO2XruuefMmC3tlqtXr57phiQwAYGFliYAAAALDAQHAACwQGgCAACwQGgCAACwQGgCAACwQGgCAACwQGgCAACwQGgCAACwQGgCAACQX/b/UdASCV1GkM4AAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "show_distribution(game_lengths(deck52))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The median game (in this sample) takes 224 plays, the mean is 294, and some games take thousands of plays.  "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
